home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / DDJMAG / DDJ9005.ZIP / MOESER.LST < prev    next >
File List  |  1990-03-23  |  13KB  |  514 lines
  1. _A MEMORY CONTROLLER_
  2. by Robert A. Moeser
  3.  
  4. [LISTING ONE]
  5.  
  6.     .
  7.     .
  8.     .
  9. typedef struct {
  10.     int anInt;
  11.     long aLong;
  12.     char tenChars[10];    /* details are unimportant */
  13. } Thing;
  14. typedef union utag {
  15.     Thing aThing;
  16.     union utag *next;
  17. } freeList;
  18.     .
  19.     .
  20.     .
  21. freeList *freeThings = 0;    /* free list, empty to begin */
  22. Thing *newThing()    /* new or recycled Thing */
  23. {
  24.     Thing *t;
  25.     
  26.     if (freeThings) {    /* any on free list? */
  27.         t = (Thing *) freeThings;
  28.         freeThings = freeThings->next;
  29.     }
  30.     else    /* no, go malloc one */
  31.         t = (Thing *) malloc(sizeof *t);
  32.     return (t);
  33. }
  34. void freeThing(theThing)    /* put Thing on freeList */
  35. Thing *theThing;
  36. {
  37.     ((freeList *) theThing)->next = freeThings;
  38.     freeThings = (freeList *)  theThing;
  39. }
  40.  
  41.  
  42. [LISTING TWO]
  43.  
  44. /* Header for memory control package 
  45.  C 1989 Robert A. Moeser, all rights reserved */
  46.  
  47. /* some things probably in your standard headers... */
  48. #ifndef __size_t
  49. #define __size_t
  50. typedef unsigned long size_t;
  51. #endif
  52.  
  53. void *malloc(size_t);
  54. void free(void *);
  55. int printf(char *, ...);
  56. int sprintf(char *, char *, ...);
  57. int scanf(char *, ...);
  58. int rand(void);
  59.  
  60. /* end of things probably in your standard headers... */
  61. typedef long counter;        /* a bit excessive, perhaps... */
  62. typedef struct _mc {
  63.     struct _mc *next;    /* used for doubly-linked list */
  64.     struct _mc *prev;    /* of all mcs */
  65.     size_t itemSize;    /* the size of the object this MCon controls */
  66.     void *freeList;     /* a free list of objects */
  67.     counter nGiven;     /* number of items handed out */
  68.     counter nOut;        /* number still out there somewhere */
  69.     counter nFree;        /* length of free list */
  70. } *MCon;
  71.  
  72. MCon newMCon(size_t theItemSize);    /* 0 = could not get storage */
  73. void *newInstanceOf(MCon theCon);    /* 0 = could not get storage */
  74. void disposeInstance(void *theItem);
  75. void purgeMCon(MCon theCon);
  76. counter disposeMCon(MCon theCon);    /* number of orphans created by action */
  77. void purgeAllMCons(void);
  78. counter disposeAllMCons(void);         /* number of orphans created by action */
  79.  
  80.  
  81.  
  82. [LISTING THREE]
  83.  
  84. /*  A Memory Controller. C 1989 Robert A. Moeser, all rights reserved */
  85.  
  86. # include "mem.h"
  87.  
  88. static void linkIn(MCon theCon);
  89. static void linkOut(MCon theCon);
  90. static int initMControl(void);
  91.  
  92. void debugCon(char *);
  93. void printCon(MCon theCon);
  94.  
  95. static MCon controlCon = 0;        /* 0 -> not yet initialized */
  96.  
  97. /* Initialize the memory control "package." Returns 1 for successful 
  98. initialization or already initialized; returns 0 if it fails. Called 
  99. automatically by newMCon, but you can call it explicity if you like. */
  100.  
  101. int initMControl(void)
  102. {
  103.     if (controlCon) return (1);        /* already initialized! */
  104.     controlCon = (MCon) malloc(sizeof *controlCon);
  105.     if (!controlCon) return (0);    /* sad but true! */
  106.     controlCon->itemSize = sizeof *controlCon;
  107.     controlCon->nGiven = controlCon->nOut = controlCon->nFree = 0;
  108.     controlCon->freeList = (void *) 0;
  109.     controlCon->next = controlCon->prev = controlCon;
  110.     return (1);                        /* OK! */
  111. }
  112.  
  113. /*  Register a new type (object) for management by the memory controller
  114. takes size of the object as an argument and returns an MCon object, which 
  115. is zero in case of failure. The Mcon object is used later to manage creation 
  116. of all instances of the new object, to maintain a free list for the object 
  117. and to keep track of demand for the object */
  118.  
  119. MCon newMCon(size_t theItemSize)
  120. {
  121.     MCon t;
  122.     int k;
  123.     k = initMControl();
  124.     if (!k) return ((void *) 0);
  125.     t = newInstanceOf(controlCon);
  126.     if (!t) return ((void *) 0);
  127.     t->itemSize = theItemSize;
  128.     t->nGiven = t->nOut = t->nFree = 0;
  129.     t->freeList = (void *) 0;
  130.     linkIn(t);
  131.     return (t);
  132. }
  133.  
  134. /* Create a new object. Takes the object's MCon as an argument (previously 
  135. created by newMCon). Returns a pointer to a new instance of the object */
  136. void *newInstanceOf(MCon theCon)
  137. {
  138.     void *t;
  139.     if (theCon->freeList) {     /* any on free list? */
  140.         t = theCon->freeList;
  141.         theCon->freeList = *((MCon *) t);
  142.         theCon->nFree--;
  143.     }
  144.     else                        /* nope, go malloc one */
  145.         t = malloc(theCon->itemSize + (sizeof theCon));
  146.     if (!t) return ((void *) 0);    /* allocator failure... */
  147.     *((MCon *) t) = theCon;     /* remember the controller */
  148.     theCon->nGiven++;
  149.     theCon->nOut++;
  150.     return ((void *) ((MCon *) t + 1));
  151. }
  152.  
  153. /* Dispose of an object. Takes a pointer to the object to dispose of
  154. the storage is kept by the object's MCon on a free list for reuse. */
  155. void disposeInstance(void *theItem)
  156. {
  157.     MCon t;
  158.     void *x;
  159.     int g;
  160.     t = *((MCon *) theItem - 1);    /* recover controllor */
  161.     t->nOut--;
  162.     t->nFree++;
  163.     *((MCon *) theItem - 1) = t->freeList;
  164.     t->freeList = (MCon *) theItem - 1;
  165. }
  166.  
  167. /* Purge the free list for an MCon. Takes the MCon whose free list should be 
  168. returned to the system storage allocator */
  169. void purgeMCon(MCon theCon)
  170. {
  171.     void *bop, *bop2;
  172.     bop = theCon->freeList;
  173.     while (bop) {
  174.         bop2 = *((void **) bop);
  175.         free(bop);
  176.         bop = bop2;
  177.     }
  178.     theCon->freeList = (void *) 0;
  179.     theCon->nFree = 0;
  180. }
  181.  
  182. /* Unregister a type. Takes the MCon object that is no longer needed
  183. returns the number of "orphans" created. Since active instances are entirely 
  184. the responsibility of clients of the memory control package, disposing of 
  185. an MCon can mean that there may be outstanding objects of the 
  186. no-longer-existing type. This is not strictly an error, but since there is 
  187. now no way to free the storage used by the orphans should be a warning sign. */
  188.  
  189. counter disposeMCon(MCon theCon)
  190. {
  191.     counter orphans = 0;    /* did this dispose create "orphans" ? */
  192.     orphans = theCon->nOut;
  193.     purgeMCon(theCon);    /* goodbye the free list */
  194.     linkOut(theCon);
  195.     disposeInstance((void *) theCon);
  196.     return (orphans);    /* number of "orphans", should be 0! */
  197. }
  198.  
  199. /* Purge the free list of every object type known to the memory controller
  200. a client might call this in a desperate attempt to satisfy a memory request */
  201. void purgeAllMCons(void)
  202. {
  203.     MCon bop;
  204.     bop = controlCon;
  205.     do {
  206.         purgeMCon(bop);
  207.         bop = bop->next;
  208.     } while (bop != controlCon);
  209. }
  210.  
  211. /* Unregister all types. This action can create orphans in the same sense as 
  212. disposeMCon above, and so returns the number. It really ought to be zero 
  213. unless the client has created objects meant to endure until program 
  214. termination. Since all types are deactivated the additional step of 
  215. deactivating the memory controller itself is taken. All storage used by the 
  216. package is returned to the system storage allocator. */
  217.  
  218. counter disposeAllMCons(void)
  219. {
  220.     counter orphans = 0;
  221.     MCon bop, bop2;
  222.     bop = controlCon->next;
  223.     while (bop != controlCon) {
  224.         bop2 = bop->next;
  225.         orphans += disposeMCon(bop);
  226.         bop = bop2;
  227.     }
  228.     purgeMCon(controlCon);
  229.     free((void *) controlCon);
  230.     controlCon = (void *) 0;    /* de-initialize mc */ 
  231.     return (orphans);    /* total number of "orphans", should be 0! */
  232. }
  233.  
  234. /* Internal Routines */
  235.  
  236. /* Link a new MCon into the doubly-linked list of all known MCons
  237. the list head and tail is the MCon for MCons, so there is always at least one
  238. item on the list and the first item is always the MCon's MCon */
  239. static void linkIn(MCon theConToAdd)
  240. {
  241.     theConToAdd->next = controlCon->next;
  242.     theConToAdd->prev = controlCon;
  243.     controlCon->next = theConToAdd;
  244.     (theConToAdd->next)->prev = theConToAdd;
  245. }
  246.  
  247. /* Unlink an MCon (called upon destruction of an Mcon */
  248. static void linkOut(MCon theConToDel)
  249. {
  250.     (theConToDel->prev)->next = theConToDel->next;
  251.     (theConToDel->next)->prev = theConToDel->prev;
  252. }
  253.  
  254. /* Debugging and Utility Routines */
  255.  
  256. /* Print a list of known MCons with statistics. Takes a tag to accompany 
  257. printout as an argument. */
  258. void debugCon(char *s)
  259. {
  260.     MCon bop;
  261.     printf("%s", s);
  262.     if (!controlCon) {
  263.         printf(" -mc is OFF!\n");
  264.         return;
  265.     }
  266.     bop = controlCon;
  267.     do {
  268.         printCon(bop);
  269.         bop = bop->next;
  270.     } while (bop != controlCon);
  271. }
  272.  
  273. /* Print one MCon. Make a quick check on the integrity of the internal 
  274. data structure. */
  275. void printCon(MCon theCon)
  276. {
  277.     char *freeBop;
  278.     int freeCount;
  279.     int OK;
  280.     freeBop = theCon->freeList;
  281.     freeCount = 0;
  282.     while (freeBop) {
  283.         freeCount++;
  284.         freeBop = *((char **) freeBop);
  285.     }
  286.     OK = freeCount == theCon->nFree;
  287.     printf("%lx = %lu\t%ld\t%ld\t%ld\t%lx\t%s\n",
  288.         theCon,
  289.         theCon->itemSize,        
  290.         theCon->nGiven,
  291.         theCon->nOut,
  292.         theCon->nFree,
  293.         theCon->freeList,
  294.         OK ? "<ok>" : "<NOK>");
  295. }
  296.  
  297.  
  298. [LISTING FOUR]
  299.  
  300. /* Part 1 of torture-test of the memory controller */
  301.  
  302. # include <stdio.h>
  303. # include <console.h>
  304.  
  305. void torture(void);
  306. main()
  307. {
  308.     int i;
  309.     for (i = 0; i < 100; i++)
  310.         torture();
  311. }
  312.  
  313.  
  314.  
  315. [LISTING FIVE]
  316.  
  317. /* Part 2 of torture-test of the memory controller */
  318.  
  319. # include "mem.h"
  320.  
  321. # define MAXTYPES        20
  322. # define MAXINSTANCES    500
  323. # define BASESIZE        25
  324. # define MAXEXTRA        25
  325. # define NPASSES        50000
  326.  
  327. void torture(void);
  328. void error(char *);
  329. void makeNewType(void);
  330. void makeNewObject(void);
  331. void freeSomeObject(void);
  332. int randle(int);
  333. void debugCon(char *);
  334. struct {
  335.     MCon mCon;
  336.     long theID;
  337. } regType[MAXTYPES];
  338. struct {
  339.     void *mObj;
  340.     long typeID;
  341. } mBag[MAXINSTANCES];
  342. int nInstances = 0;
  343. int nTypes = 0;
  344. long serialID = 1000;
  345. void torture()
  346. {
  347.     counter orphans = 0;
  348.     size_t sizeItem;
  349.     int typeIdx, objIdx;
  350.     int nPotential, nActual;
  351.     long tID;
  352.     int i, x;
  353.     long looper;
  354.     char msg[64];
  355.     for (looper = 0; looper < NPASSES; looper++) {
  356.         if (orphans) error("orphans have been created");
  357.         if (!nTypes) {
  358.             if (nInstances) error("instances but no active types");
  359.             makeNewType();
  360.         }
  361.         x = randle(10);
  362.         switch (x) {
  363.         case 0 :                /* make a report */
  364.             sprintf(msg, "loop %ld : %d instances of %d types\n",
  365.               looper,
  366.               nInstances,
  367.               nTypes);
  368.             debugCon(msg);
  369.             break;
  370.         case 1 :            /* register a new type if room */
  371.             makeNewType();
  372.             break;
  373.         case 2 :            /* make a new object if room */
  374.             makeNewObject();
  375.             break;
  376.         case 7 :            /* make many new objects */
  377.             nPotential = ((MAXINSTANCES - nInstances) >> 2) + 7;
  378.             nActual = randle(nPotential);
  379.             while (nPotential--)
  380.                 makeNewObject();
  381.             break;
  382.         case 3 :            /* free an object if any exist */
  383.             freeSomeObject();
  384.             break;
  385.         case 8 :            /* free many objects */
  386.             nPotential = ((MAXINSTANCES - nInstances) >> 3) + 3;
  387.             nActual = randle(nPotential);
  388.             while (nPotential--)
  389.                 freeSomeObject();
  390.             break;
  391.         case 4 :      /* purge free list of a type if any exist */
  392.             if (nTypes) {
  393.                 typeIdx = randle(nTypes);
  394.                 purgeMCon(regType[typeIdx].mCon);
  395.             }
  396.             break;
  397.         case 9 :                /* purge a number of free lists */
  398.             if (nTypes) {
  399.                 nActual = randle(nTypes);
  400.                 for (i = 0; i < nActual; i++) {
  401.                     typeIdx = randle(nTypes);
  402.                     purgeMCon(regType[typeIdx].mCon);
  403.                 }
  404.             }
  405.             break;
  406.         case 5 :     /* free all of a registered type if any exist */
  407.             if (nTypes) {
  408.                 typeIdx = randle(nTypes);
  409.                 tID = regType[typeIdx].theID;
  410.                 for (i = 0; i < nInstances; )
  411.                     if (mBag[i].typeID == tID) {
  412.                         disposeInstance(mBag[i].mObj);
  413.                         nInstances--;
  414.                         mBag[i] = mBag[nInstances];
  415.                     }
  416.                     else i++;
  417.                     /* and maybe kill the controllor */
  418.                 if (randle(13) > 7) {
  419.                  orphans += disposeMCon(regType[typeIdx].mCon);
  420.                  nTypes--;
  421.                  regType[typeIdx] = regType[nTypes];
  422.                 }
  423.             }
  424.             break;
  425.         case 6 :             /* free all instances of all types */
  426.             if (randle(20) < 15) break;
  427.             for (i = 0; i < nInstances; i++)
  428.                 disposeInstance(mBag[i].mObj);
  429.             nInstances = 0;
  430.                     /* kill some controllors */
  431.             for (i = 0; i < nTypes;)
  432.                 if (randle(15) > 13) {
  433.                       orphans += disposeMCon(regType[i].mCon);
  434.                       nTypes--;
  435.                       regType[i] = regType[nTypes];
  436.                 }
  437.                 else i++;    
  438.                /* and maybe kill all the rest and shut down! */
  439.             if (randle(20) > 17) {
  440.                 orphans += disposeAllMCons();
  441.                 nTypes = 0;
  442.             }
  443.             break;
  444.         }
  445.     }
  446.     printf("\n%ld passes...\n", NPASSES);
  447. }
  448. void makeNewType()
  449. {
  450.     MCon tCon;
  451.     size_t sizeItem;
  452.     if (nTypes < MAXTYPES) {
  453.         sizeItem = BASESIZE + randle(MAXEXTRA);
  454.         tCon = newMCon(sizeItem);
  455.         if (!tCon) {
  456.             error("could not make controllor");
  457.             return;
  458.         }
  459.         regType[nTypes].mCon = tCon;
  460.         regType[nTypes].theID = serialID++;
  461.         nTypes++;
  462.     }
  463. }
  464. void makeNewObject()
  465. {
  466.     int typeIdx;
  467.     void *tObj;
  468.     if ((nInstances < MAXINSTANCES) && nTypes) {
  469.         typeIdx = randle(nTypes);
  470.         tObj = newInstanceOf(regType[typeIdx].mCon);
  471.         if (!tObj) {
  472.             error("could not get object memory");
  473.             return;
  474.         }
  475.         mBag[nInstances].mObj = tObj;
  476.         mBag[nInstances].typeID = regType[typeIdx].theID;
  477.         nInstances++;
  478.     }
  479. }
  480. void freeSomeObject()
  481. {
  482.     int objIdx;
  483.     if (nInstances) {
  484.         objIdx = randle(nInstances);
  485.         disposeInstance(mBag[objIdx].mObj);
  486.         nInstances--;
  487.         mBag[objIdx] = mBag[nInstances];
  488.     }
  489. }
  490. void error(char *s)                    /* print error message and hang */
  491. {
  492.     char hang[12];
  493.     printf("\nERROR : %s\n", s);
  494.     scanf("%s", hang);
  495. }
  496. randle(int n)                         /* random number up to not including n */
  497. {
  498.     if (n <= 0) error("bogus randle call");
  499.     return (rand() % n);
  500. }
  501.  
  502.  
  503. [Examplσ 1║ Thσ K&╥ tnodσ allocator]
  504.  
  505.     struct tnode *talloc()
  506.     {
  507.         char *malloc();
  508.         return ((struct tnode *) malloc(sizeof(struct tnode)));
  509.     }
  510.  
  511.  
  512.  
  513.  
  514.